import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:快排的优化与归并排序
 * User: Admin
 * Date: 2022-06-01
 * Time: 17:36
 */
public class TestDemo {
    public static void quickSort1(int[] array,int left,int right) {
        Stack<Integer> stack = new Stack<>();

        int pre = partition(array,left,right);

        if(pre > left+1) {
            stack.push(left);
            stack.push(pre-1);
        }

        if(pre < right - 1) {
            stack.push(pre+1);
            stack.push(right);
        }

        while(!stack.empty()) {
            right = stack.pop();
            left = stack.pop();

            pre = partition(array,left,right);

            if(pre > left+1) {
                stack.push(left);
                stack.push(pre-1);
            }

            if(pre < right - 1) {
                stack.push(pre+1);
                stack.push(right);
            }
        }
    }

    public static int midIndexOf(int[] array,int left, int right) {
        int mid = (left+right)>>>1;

        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            } else if(array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        }else {
            if(array[mid] > array[left]) {
                return left;
            }  else if(array[mid] < array[right]) {
                return right;
            } else {
                return mid;
            }
        }

    }
    public static void insertSort(int[] array,int left , int right) {
        for (int i = left+1; i <= right; i++) {
            int tmp = array[i];
            int j = 0;
            for (j = i-1; j >= left ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    public static void Swap(int[] array, int left ,int right) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;
    }

    public static int partition(int[] array, int left, int right) {
        int tmp = array[left];//基准
        int index = left;

        while(left < right) {

            while(left < right && array[right] >= tmp) {
                right--;
            }

            while(left < right && array[left] <= tmp) {
                left++;
            }


            Swap(array,left,right);
        }

        Swap(array,left,index);

        return left;
    }

    public static void quickSort(int[] array, int left ,int right) {
        if(left >= right) return;
        //优化一：插排
        if(right - left <= 5) {
            insertSort(array,left,right);
        }

        //优化二：三数取中
        int index = midIndexOf(array,left,right);
        Swap(array,index,left);


        int pre = partition(array,left,right);
        quickSort(array,left,pre-1);
        quickSort(array,pre+1,right);
    }

    public static void merge(int[] array,int left,int right,int mid) {
            int a1 = left;
            int a2 = mid;
            int e1 = mid+1;
            int e2 = right;

            int[] tmpArr = new int[right-left+1];
            int k = 0;
            while(a1 <= a2 && e1 <= e2) {

                if(array[a1] <= array[e1]) {
                    tmpArr[k++] = array[a1++];
                } else {
                    tmpArr[k++] = array[e1++];
                }

            }

            while(a1 <= a2) {
                tmpArr[k++] = array[a1++];
            }

            while(e1 <= e2) {
                tmpArr[k++] = array[e1++];
            }

        for (int i = 0; i < k; i++) {
            array[i+left] = tmpArr[i];
        }
    }

    public static void mergeSort(int[] array, int left ,int right) {
        if(left >= right) return;

        int mid = (left+right)/2;

        mergeSort(array,left,mid);
        mergeSort(array, mid+1, right);

        merge(array,left,right,mid);
    }

    public static void main(String[] args) {
        int[] array = {3,9,1,2,8,7,6,5};
        //归并排序
        /*mergeSort(array,0,array.length-1);*/
        //快熟排序
        /*quickSort(array,0,array.length-1);*/
        quickSort1(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}
